package java_0220.leetcode;

import java.util.Scanner;

/**
 * 编一个程序，读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树（以指针方式存储）。
 * 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。
 * 建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
 */
public class JZkY11_BuildBinTreeByPreOrder {
    public static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(char val) { this.val = val; }
        TreeNode(char val,TreeNode left,TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()){
            String str=scanner.next();
            TreeNode root=preOrderBuilder(str);
            inOrder(root);
            System.out.println();
        }
    }

    private static void inOrder(TreeNode root) {
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    //index表示前序遍历当前处理到哪个字符
    private static int index=0;
    private static TreeNode preOrderBuilder(String str) {
        char cur=str.charAt(index);
        //判断处理的字符是否为#，即是否为空
        if(cur=='#'){
            //空节点，不构建节点
            return null;
        }
        //不为空，先构建根节点,同时index向后处理下一个字符
        TreeNode root=new TreeNode(cur);
        index++;
        //递归处理左右子树
        root.left=preOrderBuilder(str);
        index++;
        //递归处理右子树
        root.right=preOrderBuilder(str);
        return root;
    }
}
